package main.java;

import java.util.Stack;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-07-26 20:11
 */
public class Test09_包含min函数的栈 {

    /**
     * 题目：
     * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，
     * 调用 min、push 及 pop 的时间复杂度都是 O(1)。
     * <p>
     * 思路：
     * 首先 正常的push 和pop操作时间复杂度都是O（1）
     * 但是通过min函数得到栈中最小的元素 必然要遍历整个栈，那么时间复杂度就为O（n）了
     * 因此一个栈是无法完成的，结合用两个栈实现队列这道题，应该也是同样的，
     * 一个负责插入，删除操作，一个负责记录最小值
     */

    class MinStack {
        Stack<Integer> stack1;
        Stack<Integer> stack2;

        public MinStack() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }

        public void push(int x) {
            stack1.push(x);
            if (stack2.isEmpty() || stack2.peek() >= x) {
                stack2.push(x);
            }

        }

        public void pop() {
            if (stack1.peek().equals(stack2.peek())) {
                stack1.pop();
                stack2.pop();
            } else {
                stack1.pop();
            }
        }

        public int top() {
            return stack1.peek();
        }

        public int min() {
            return stack2.peek();
        }
    }
}
